#约瑟夫环问题的三种解决方案
import numpy as np

#第一种解决方案，使用数组来解决约瑟夫环
def joseph_ring_array(total_number,interval):
    state=np.zeros((total_number+1), int)#产生全为0的数组，数组中的元素表示人的状态，0表示未出局，1表示已经出局。
    out_order=np.zeros((total_number), int)#产生数组，用来存放出局人的编号
    count=interval_number=0 #count：记录出局的人数；serial_number：编号；interval_number:报数值
    serial_number=-1
    while count!=total_number:
        serial_number=serial_number+1
        if serial_number>=total_number: serial_number=0#当编号超出total_number时，需要重新进行编号
        if state[serial_number]==0:#未出局的人才可以计数
            interval_number=interval_number+1
            if interval_number==interval:#当某人报数为interval时，表示他要出局
                state[serial_number]=1
                out_order[count]=serial_number
                count=count+1
                interval_number=0
    return out_order

#第二中解决方案：使用递归来解决约瑟夫环问题
def recursion(total_number,interval,serial_number):#total_number的值随着递归的编号在不断的编变化
    #第一轮出局的编号：(interval-1)%total_number
    if serial_number==1:
        return ((interval-1)%total_number)
    #新一轮中的编号: (旧一轮中的编号-最大报数值M) %旧一轮中的总人数
    #旧一轮中的编号: (新一轮的编号+最大报数值M) %旧一轮中的总人数
    return ((recursion(total_number-1,interval,serial_number-1)+interval)%total_number)

def joseph_ring_recursion(total_number,interval):
    out_order=np.zeros((total_number), int)#产生数组，用来存放出局人的编号
    serial_number=0
    while(serial_number!=total_number):
        serial_number=serial_number+1
        serial=recursion(total_number,interval,serial_number)
        out_order[serial_number-1]=serial
    return out_order

s=joseph_ring_array(3,2)
print(s)
m=joseph_ring_recursion(3,2)
print(m)
